The invention relates to a method for scheduling reading data from a storage medium for consumption by users in the form of a plurality of data streams, wherein each of the data streams has an identical maximum consumption rate of R.sub.max data elements per second; said method comprising the steps of:
(i) dividing a predetermined period of t.sub.cycle seconds into n successive time intervals, each of t.sub.interval seconds; PA1 (ii) reserving for each data stream a corresponding buffer capable of storing at least R.sub.max *(n+1)*t.sub.interval data elements PA1 (iii) arranging the data streams in a plurality of distinct groups; PA1 (iv) reading data for each data stream of a first one of said groups from the storage medium in one sweep and storing the data in the corresponding buffer. PA1 (i) dividing a predetermined period of t.sub.cycle seconds into n successive time intervals, each of t.sub.interval seconds; PA1 (ii) reserving for each data stream a corresponding buffer capable of storing at least R.sub.max *(n+1)*t.sub.interval data elements PA1 (iii) arranging the data streams in a plurality of distinct groups; and PA1 (iv) causing the reader to read data for each data stream of a first one of said groups from the storage medium in one sweep and to store the data in the corresponding buffer. PA1 arranging the data streams in at most n preliminary groups g.sub.1 to g.sub.n, where g.sub.1, corresponds to the first group, by determining for each data stream a minimum number i=1 to n such that the buffer corresponding to the data stream comprises less then R.sub.max *(i+1)*t.sub.interval data elements and assigning the data stream to group g.sub.i ; and PA1 reassigning the data streams to the preliminary groups by successively checking the preliminary groups g.sub.n to g.sub.2 by: verifying whether the data for all data streams of group g.sub.i (i=n to 2) can be read within t.sub.interval seconds; if not: repeatedly selecting a data stream of group g.sub.i and removing the selected data stream from group g.sub.i until the data for all remaining data streams of group g.sub.i can be read within t.sub.interval seconds; and assigning the selected data streams to an earlier group g.sub.j (=1 to i--1). PA1 selecting a halted data stream for which a re-start signal has been received; and PA1 assigning the selected data stream to the first group. PA1 selecting a new data stream for which an inclusion request has been received; and PA1 assigning the selected data stream to the first group.
The invention further relates to a system for reading data from a storage medium and supplying the data in the form of a plurality of data streams for consumption to users, wherein each of the data streams has an identical maximum consumption rate of R.sub.max data elements per second; said system comprising: a plurality of buffers for storing data; a reader for reading data from the storage medium and storing the read data in at least one of the buffers; and a scheduler for controlling the reader by:
A method and system of this kind are used in a multimedia server and, more specifically, in a video on demand server. A general requirement in such systems is to supply a continuous, un-interrupted stream of data to each active user. Typically data is read from a conventional storage medium, such as hard disks which are usually arranged in a disk array, such as a RAID system. To supply data to a user as a continuous data stream, special scheduling schemes for reading data from the disks are required with an appropriate scheme for temporarily buffering the read data before the data is supplied to the user. In general a distinction can be made between a fixed consumption rate and a variable consumption rate system.
In a fixed consumption rate system data is typically supplied to a user as a fixed rate data stream. Usually the rate is identical for each stream in the system. An example of such a system is a near-video-on-demand system, wherein a number of films can be played in parallel and the same film may be played several times in parallel, where regularly, for instance, every five or fifteen minutes, a new copy of the same film is started. A conventional scheduling algorithm for a fixed consumption rate system is the so-called SCAN algorithm. In this algorithm at fixed regular intervals for each stream a fixed amount of data (sufficient to last one period) is read and stored in the buffer. Typically, for each stream a buffer with capacity for storing two blocks is used; one for reading data from the disk and one for supplying data to the user(s). Reading from the disk occurs in one sweep (e.g. from the outer edge to the inner edge of the disk or vice versa) for all streams. Disk access is in the order in which the data for the streams happens to be located on the disk. Typically, the sweep and the buffer reading are synchronised: the buffers for all streams are read from the same buffer position and a new sweep is started at the moment when all read positions change from one block to the other (implying that in each buffer a block has become empty). The maximum duration of a sweep corresponds to the time required for the application to read a block from the buffer. No pre-conditions are made for storing the data on the disk, implying that a specific stream in one sweep may be serviced first and in a next sweep may be serviced last. As a consequence, a buffer of twice the block size is required.
In a variable consumption rate system the rate at which a user consumes data varies over time. Typically, a maximum consumption rate can be defined for each data stream. In practice, usually an identical maximum consumption rate is used for all streams, although it may be possible to efficiently support streams with different maximum consumption rates (e.g. one maximum for an audio stream and another maximum for a combined video and audio stream). Variable consumption rate systems are, for instance, used for systems which support VCR-like functions such as pause or slow motion, or systems which use a data compression scheme with a variable bit rate, such as MPEG-2. The SCAN algorithm can also be used for a variable consumption rate system with a defined maximum rate. Due to the variable rate, different streams may empty one of the buffer blocks at different moments. To be prepared for the worst case for each stream a buffer of three blocks is required (e.g. at the beginning of a sweep a stream had almost emptied a block (resulting in the stream being skipped for this sweep, since no entire block can be read); at the beginning of the next sweep, the stream has almost emptied two blocks (resulting in one block being loaded in this sweep); to cope with the situation that the stream may be serviced last during this sweep, a total of three blocks are required).
For fixed consumption rate systems, an improvement to the SCAN algorithm is known from "Design and Analysis of a Grouped Sweeping Scheme for Multimedia Storage Management" of P. S. Yu, M. Chen, D. D. Kandlur in Lecture Notes in Computer Science 712: Network and Operating System Support for Digital Audio and Video. According to the Grouped Sweeping Scheme (GSS) a total number of N data streams are divided in n groups. In one overall period of t.sub.cycle seconds a sweep is performed for each group, where the groups are serviced in a fixed order (cyclically servicing in a fixed sequence, usually referred to as Round Robin servicing). For each sweep a maximum duration of t.sub.interval sec. is reserved, where m*t.sub.interval=t.sub.cycle. A stream is fixedly assigned to a group. Due to this fixed assignment, it is excluded that a stream is serviced first in one period and last in the following period. As such the buffer requirements are reduced from two large blocks to m+1 small blocks. Roughly speaking, the duration of the m sweeps corresponds to one large sweep in the SCAN system and n small blocks to one large block of the SCAN algorithm. Since in reality m small sweeps take longer than one large sweep, the actual savings in buffering are less. For each system an optimum number of groups can be calculated. Although in principle streams are fixedly assigned to groups, reallocation may occur in between cycles, for instance to achieve a better balance between the groups caused by streams leaving the system. To reallocate a stream some additional buffering and pre-fetching is required.
The fixed nature of the GSS system results in relatively long delays before new streams can be accepted by the system. The system is also not suited for handling variable consumption rate streams.